For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

1
vote
1answer
345 views

Probability that subsets intersect

Given a set $N$ I would like to calculate the probability that two arbitrarily chosen and equally likely subsets $K\subseteq N$ and $J\subseteq N$ both of fixed size intersect. Let's say $n=\#N$, ...
1
vote
1answer
56 views

Calculating upper eccentricity in a graph

I was going through a paper. There calculating upper eccentricity was mentioned. Can anybody help me in finding out how it was done? I tried hard but was unable to get it. A little hint or explanation ...
2
votes
1answer
126 views

Number array divided into several parts, genelize $a>b>c>d>0$ so $ab+cd>ac+bd$ to more numbers

Now, we have an original number array: $$a_1 > a_2 > a_3 > ... > a_{mn} > 0$$, I wonder whether the following inequality is the truth, if so, could you give me the proof or some ...
7
votes
3answers
377 views

Perfect squares using 20 1's, 20 2's and 20 3's.

How many perfect squares can be formed using 20 1's, 20 2's and 20 3's. This is a recent exam question, which I had no clue how to solve? There is some kind of trick here, since time allotted to ...
2
votes
3answers
60 views

Proving an identity algebraically

Show that $$\sum_{i=0}^{n} \binom{n}{i} i (i-1)=n(n-1)2^{n-2}$$ knowing that $$\sum_{i=0}^{n}\binom{n}{i}i=n2^{n-1}$$ I ended up after a while with ...
2
votes
1answer
149 views

Godsil & Royle, Theorem 9.5.1: Extension for digraphs?

I was wondering if there is an extension to digraphs for Theorem 9.5.1 in Godsil & Royle's Algebraic Graph Theory. The Theorem can also be found in Willem Haemers paper Interlacing Eigenvalues ...
2
votes
2answers
195 views

Partitions of $n$: proving $p(n+2)+ p(n) \geq 2p(n+1)$

For $n \geq 2$ give an alternative description of $p(n) - p(n-1)$ as the number of partitions of $n$ which have a certain property. I have done that part, it is fine. I have not included it here ...
3
votes
1answer
112 views

Probabilistic Proof of Hook Length Formula

I am currently trying to understand the probabilistic proof for hook-length formula for standard young tableaux of a given shape but at some step of the proof I am confused. I will attach a picture of ...
3
votes
0answers
29 views

relation between eccentricity and weiner index

I was going through a topic $Weiner$ $Index$. Is there any relation between eccentricity of the graph and the Weiner Index of the graph. Any hint or link will be appreciated. thanks a lot. NOTE: ...
7
votes
2answers
357 views

Painting chess board

The task is to paint each of the 64 squares on a chess board either blue or red. I need to find the number of distinct ways this can be done given that any 2x2 square on the board has two red and two ...
2
votes
2answers
75 views

example of a particular type of graph

I am searching for those classes of graphs where distance between any two vertices of the graph is $d$. Are there such type of graphs, after leaving the $Complete Graphs, K_n$. Thanks for your help.
3
votes
2answers
159 views

Geometric solution to classic committee problem

Most people know the classic committe style problems. I read this solution to one of the basic version of the committe problem and was impressed, but not sure why it works. I was hoping someone ...
2
votes
1answer
56 views

Number of Total orders of a dependency graph

Define a dependency graph to be a graph $G=(V,E)$ such that an edge between vertices $v$ and $u$ in $V$ is present if $v<u$ i.e. $v$ comes before $u$ in our ordering (I'm not very concise here, I ...
2
votes
1answer
167 views

Counting flower and committee questions

$1$) You want dozen roses. The florist has white, pink, red, and violet roses. How many possible ways could you make the order? $2$) There are $35$ men and $15$ women. Committee needs to have four ...
3
votes
0answers
65 views

Boolean combinatorics

Every finite Boolean algebra has a "middle layer", corresponding to the subsets of size $n/2$ (when looking at the algebra of subsets of $[n]$) or to a set of formulas including $p_i, \neg p_i, p_i ...
2
votes
0answers
82 views

A combinatorics problem that seems faulty

I've come across the following problem. Show that the number of elements of $X$ belonging to a least $r$ of the sets $A_1,\ldots,A_n\subset X$ is $$\sum_{k=r}^n(-1)^{k-r}{k-1\choose ...
3
votes
2answers
135 views

Distribution of $n$ balls to 10 cells; Inclusion-exclusion problem

So I got another ( :[ ) problem I got stuck with. So before I get going with that, I would like to know if you know any places where I can learn the principles of these subjects (compositions, ...
37
votes
5answers
762 views

Closed form for $\prod_{n=1}^\infty\sqrt[2^n]{\frac{\Gamma(2^n+\frac{1}{2})}{\Gamma(2^n)}}$

Is there a closed form for the following infinite product? $$\prod_{n=1}^\infty\sqrt[2^n]{\frac{\Gamma(2^n+\frac{1}{2})}{\Gamma(2^n)}}$$
1
vote
1answer
64 views

Combinatorics identity sum of

Prove that: $$\sum^{n}_{k=0}\binom{k}{2n-k}2^k = 2^{2n}$$ By using only combinatorics identities.
2
votes
1answer
55 views

Even weighted codewords and puncturing

My question is below: Prove that if a binary $(n,M,d)$-code exists for which $d$ is even, then a binary $(n,M,d)$-code exists for which each codeword has even weight. (Hint: Do some puncturing ...
3
votes
1answer
156 views

Formula for lines that can be drawn using $n$ points

Please help me! How many lines can be drawn using $6$ points? Each line is made by connecting $2$ points.
2
votes
2answers
412 views

How to prove using Ferrer's diagrams?

Using Ferrer's diagrams, show that the number of partitions of $n$ into parts of size 1 or 2 is equal to the number of partitions of $n$ into two parts.
2
votes
1answer
118 views

An interesting version of the problem “balls into bins”

Consider n people, each has k identical balls. Each people choose k different bins from m bins, constrained by the condition that there are no two people choose exactly the same k bins. For instance, ...
2
votes
1answer
336 views

Odds of Choosing Items out of a bag

Let's say there is a bag filled with a myriad of balls, labeled 1 through 7. There are an infinite number of each ball (i.e. odds don't diminish when one is removed). Edit A better phrasing than ...
1
vote
3answers
73 views

Proof that $\sum_{k=0}^m \binom{m}{k}\frac{1}{k+1} = \frac{2^{m+1}-1}{m+1}$ [duplicate]

Recently I needed to compute $E[\frac{1}{X+1}]$ where $X\sim Bin(m, \frac 1 2)$. While expanding, I came across the sum $\sum_{k=0}^m \binom{m}{k}\frac{1}{k+1}$, which I was unable to solve. Plugging ...
7
votes
4answers
330 views

Proof of the identity $2^n = \sum\limits_{k=0}^n 2^{-k} \binom{n+k}{k}$

I just found this identity but without any proof, could you just give me an hint how I could prove it? $$2^n = \sum\limits_{k=0}^n 2^{-k} \cdot \binom{n+k}{k}$$ I know that $$2^n = ...
4
votes
2answers
502 views

How many numbers from $1$ to $99999$ have a digit-sum of $8$?

How many numbers from $1$ to $99999$ have a digit-sum of $8$? Why is the answer ${8+4\choose 4}$? Does the following method work? Answer is the number of ways to split 8 into 5 digits, i.e. ...
4
votes
1answer
456 views

How many vertices of degree 3 or more can a tree have at most?

It is known that a tree $T=(V,E)$ has at least $\Delta$ leaves, where $\Delta$ is the maximum degree of $T$. But how many vertices of specific degree at least $k$ can a tree have at most? I'm ...
3
votes
0answers
163 views

Combinatorics: Distributions with several constraints - potential generating sequences?

This seems to be a "stars and bars problem" - however I am unsure how to apply a constraint. Furthermore, I would like to understand how this would be done in both counting as well as generating ...
4
votes
3answers
437 views

Counting the numbers between $1$ and $1,000,000$ whose digits sum to $30$

What's the number of numbers between $1$ and $1,000,000$ whose digits sum is $30$? So I thought of this as a stars and sticks problem, so in the case you have $35\choose 5$ numbers whose sum is ...
13
votes
3answers
1k views

Combinatorial proof of $\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$.

Prove that $$\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$$ I can't find counting interpretations for either of the sides. A hint of "if $S$ is a subset of $\{1, . . . , n\}$ and $S^\prime$ is its ...
2
votes
3answers
632 views

How many numbers between 1 and 10,000,000 don't have the sequence 12? Inclusion-exclusion problem

I got the following question: How many numbers between 1 and 10,000,000 don't have the sequence 12? This is an inclusion-exclusion problem. Sadly I didn't fully understand its concept, so I tried ...
3
votes
3answers
123 views

Weird $3^n$ in an identity to be combinatorially proved

Give a combinatorial proof of the following identity: $$3^n=\sum_{i=0}^{n}\binom{n}{i}2^{n-i}$$ I can't see any counting argument that would yield $3^n$, and the right hand side is also pretty ...
2
votes
1answer
413 views

Proving an identity with a combinatorial proof

For any integers $n$, $k$, $r$ where $n\geq k\geq r \geq 0$, give a combinatorial proof of the following identity: $$\binom{n}{k}\binom{k}{r}=\binom{n}{r}\binom{n-r}{k-r}$$ The problem is that I ...
4
votes
2answers
165 views

Subgroup transitive on the subset with same cardinality

Maybe there is some very obvious insight that i miss here, but i've asked this question also to other people and nothing meaningful came out: If you have a subgroup G of $S_n$(the symmetric group on ...
1
vote
1answer
95 views

A permutation problem

Consider all the permutations of the digits $1, 2, \dots, 9$. Find the number of permutations each of which satis fies all of the following: 1) the sum of the digits lying between 1 and 2 (including ...
13
votes
1answer
2k views

How to find the smallest number with just $0$ and $1$ which is divided by a given number?

Every positive integer divide some number whose representation (base $10$) contains only zeroes and ones. One can easily prove that using pigeonhole principle. ...
3
votes
1answer
763 views

Distinguishable balls in distinguishable boxes

I wish to improve on my combinatorial reasoning skills and my step-father gave me this problem that has left me quite confused. It seems to me that because the balls are colored similar to the boxes, ...
0
votes
3answers
416 views

Good books on combinatorics

I have a math Ph.D. but my knowledge of combinatorics sucks and I simply don't know how to compute anything more complicated, i.e. what happens when we put restrictions on the allowed configurations ...
6
votes
1answer
311 views

Colored balls puzzle

Imagine you have $n$ balls in a bag that are colored from $1$ to $n$. At each turn you take two balls at random out that have different colors and color one the color of the other. You then put them ...
1
vote
1answer
272 views

Weight enumerator of the Hamming code

Let $H_r$ be the usual Hamming code of length $2^r-1$. What is the weight enumerator of $H_r^\perp$? Using this find an expression for the weight enumerator of $H_r$. (we are in binary case)
1
vote
1answer
370 views

Math Behind the Game “Quoridor”

I'm going to write an article for middle school students to introduce them to the game "quoridor". Tha game certainly is interesting, but it will be great to add to the article some serious "math ...
3
votes
1answer
118 views

Determining probability of certain combinations

Say I have a set of numbers 1,2,3,4,5,6,7,8,9,10 and I say 10 C 4 I know that equals 210. But lets say I want to know how often 3 appears in those combinations how do I determine that? I now know the ...
1
vote
2answers
85 views

Choosing elements from sets

OK, so I've always been terrible at combinatorics and I'm trying to generalize some combinatorial problems and I can't figure out where I'm going wrong. Take the following problem: Assume we are ...
3
votes
1answer
108 views

Finding number of functions in set A [duplicate]

Let $A = \{1, 2, 3, 4, \ldots, n\}$ (it follows that: $|A| = n$). My objective is to count the number of functions: $f: A \rightarrow A$, that are monotonically increasing, i.e. $f(x) \leq f(x + 1)$, ...
1
vote
3answers
113 views

About the Pigeonhole principle

The principle says that: Let $k$ and $n$ be any two positive integers. If at least $kn+1$ objects are distributed among $n$ boxes, then one of the boxes must containat least $k+1$ objects. In ...
7
votes
1answer
95 views

Topology of Forum Posts

Okay, so here's an interesting question regarding web forums. Let's say you have a typical forum, such as the comments section on a blog, or whatnot. Viewers can post comments in response to either ...
6
votes
2answers
336 views

Binomial probability with summation

Show that $$\sum_{k=0}^{m} \frac{m!(n-k)!}{n!(m-k)!} = \frac{n+1}{n-m+1}$$ Attempt: It becomes: $$\sum_{k=0}^{m } \frac{\binom{m}{k}}{\binom{n}{k}}$$ Telescoping, pairing, binomial theorem don't ...
0
votes
2answers
118 views

$a_{k+1}-a_k = a_2 - a_1$,$\sum \limits_{k=1}^{n}{a_k}$=?

I need to find an explicit formula for the sum $\sum \limits_{k=1}^{n}{a_k}$ where $(a_k)_{k∈ℕ}∈ℚ^ℕ$ with $a_{k+1}-a_k = a_2 - a_1$ for all k∈ℕ I would love to start with by collecting the values of ...
1
vote
1answer
292 views

No of labeled trees with n nodes such that certain pairs of labels are not adjacent.

What is the number of trees possible with $n$ nodes where the $i$th and $(i+1)$th node are not adjacent to each other for $i \in \left[0,n-1\right)$ and $$i/2 = (i+1)/2.$$ (integer division) (nodes ...