This tag is for basic 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)

3
votes
2answers
83 views

Deriving a (tricky, I think?) recurrence relation

I'm having trouble trying to derive a recurrence relation for a problem I'm looking at. "Let $h_n$ be the number of ways of packing a bag with $n$ fruits (either apples, oranges, bananas, or pears), ...
1
vote
0answers
42 views

Arranging Peoples In A Row

Why when we need to put 2 people together we calculate them as one unit and not two? They have 2 ways to sit one near the other, but why we reduce just 1 from the overall number of peoples?
0
votes
1answer
46 views

Summation of product of combinations

my question is, can the following series be solved $$ \sum_{i,j}^{} {a\choose i} {b \choose j} $$ where, (i+j) mod 3 =0 or i+j is multiple of 3 I need a generalized solution, i.e variables i,j,k... ...
0
votes
2answers
70 views

Grasshopper in a tropical forest

There is a Grasshopper in a tropical forest. The grasshopper can jump only vertically and horizontally, and the length of the jump is always equal to x centimeters. A Grassshopper has found herself at ...
0
votes
1answer
39 views

Differences Exponential and Ordinary Generating Functions

I am trying to understand conceptually the differences between ordinary generating functions (OGF$=1+x+x^2+\ldots$ ) and exponential generating functions (EGF$=1+x+\frac{x^2}{2!}+\ldots$ ) when it ...
4
votes
0answers
76 views

How to prove this indentity $\binom{100}{0}^2-\binom{100}{1}^2+\binom{100}{2}^2-…-\binom{100}{99}^2+\binom{100}{100}^2=\binom{100}{50}$ [duplicate]

I don't know how to prove this identity: $\binom{100}{0}^2-\binom{100}{1}^2+\binom{100}{2}^2-\binom{100}{3}^2+...-\binom{100}{99}^2+\binom{100}{100}^2=\binom{100}{50}$
1
vote
2answers
35 views

How many ways are there to pick 18 letters from 12 A's and 12 B's?

How many ways are there to pick 12 letters from 12 A's and 12 B's? How many ways are there to pick 18 letters from 12 A's and 12 B's?
2
votes
1answer
40 views

How do you handle this kind of probability?

What is the probability of selecting a singular matrix from $\Bbb{R}^{3\times 3}$? I calculated it to be zero based on their being approximately $9$ degrees of freedom to choose entries of $A$ such ...
1
vote
1answer
55 views

How find this number of permutation such $|a_{k}-k|\ge\dfrac{n-1}{2}$

let $n$ is give postive integer,Find the number of the $(a_{1},a_{2},\cdots,a_{n})$ be a permutation of $(1,2,3,\cdots,n)$.such $$|a_{k}-k|\ge\dfrac{n-1}{2}$$for any $k=1,2,\cdots,n$ This is ...
1
vote
1answer
39 views

How to prove a set must have a specific number of elements?

Trying to understand sets but having a hard time. Could someone help me through this one? Let A be a set of six positive integers each of which is less than 13. Show that there must be two distinct ...
2
votes
1answer
34 views

counting vector pairs with a given hamming distance

Let $\mathbb{F}_2$ denote the binary field. For integer $t\geq 0$, define $W_t = \{(x,y)\in \mathbb{F}_2^n\times \mathbb{F}_2^n: d_H(x,y)=t\}$, where $d_H(\cdot,\cdot)$ denotes the Hamming distance. ...
0
votes
2answers
23 views

Minimum of Maximum of Addition of two vectors/arrays

Suppose you have two arrays and you want to compute the maximum of the addition of the two arrays. Now you move the second array one field to the right. Now you can compute the maximum again of the ...
4
votes
1answer
75 views

Proving a combinatorial identity “directly”

This is a homework problem. In the first part of the problem, I managed to use a combinatorial problem to prove the following identity: $\Sigma_{k=0}^{n}(-1)^k {2n-k \choose k} 2^{2n-2k} = 2n+1$ But ...
1
vote
1answer
28 views

Number [n,k]-linear codes with one fixed vector

I need to find the number of $[n,k]$-linear binary codes with one fixed codeword x (non zero) in it. So I guess, I need to count the number of $k$-dimensional ...
1
vote
2answers
26 views

$K$ events that are $(K-1)$-wise Independent but not Mutually/Fully Independent

I had the following question: Construct a probability space $(\Omega,P)$ and $k$ events, each with probability $\frac12$, that are $(k-1)$-wise, but not fully independent. Make the sample space as ...
0
votes
0answers
19 views

finding the least non-zero of a multivariable polynomial

Let $P(x_1,x_2,...,x_m)$ be a homogeneous polynomial of degree n, with integers coefficients. How can you find the least* $a=(a_1,a_2,...,a_m)$, where $a_i$ are positive integers and $P(a)!\neq 0$? ...
0
votes
1answer
26 views

Inclusion Exclusion Principle Question

A merchant have 3 kinds of coins in his pocket: r of copper, s of aluminum and t of gold. He randomly take out 3 coins from his pocket. how much combinations there are in which he will pull 3 coins ...
1
vote
0answers
56 views

Number of paths in a grid

A common puzzle problem is to count the number of paths that start from the bottom-left-hand corner of a grid and end at the top-right hand corner, with the restriction that you can only move upwards ...
1
vote
1answer
26 views

Partitioning N people into N/2 sized groups across N - 1 days

Problem Statement: Given a list of $N$ people. On the 1st day, divide them into $N/2$ groups of two people each. On the 2nd day, divide them into groups of two again... Do this every day, until day ...
1
vote
0answers
14 views

Generalized permutahedron and random polytopes

The Birkhoff polytope $B_n$ is defined as the convex hull of the set of permutation matrices, which gives us the set of doubly stochastic matrices. A concept which is intimately related is that of the ...
0
votes
1answer
55 views

Number of seating arrangements in 5 cars

An exercise from Introductory Combinatorics by Richard A.Brualdi: A roller coaster has five cars, each containing four seats, two in front and two in back. There are 20 people ready for a ride. ...
0
votes
1answer
14 views

number of elements in unsortet case

I have a group M with Mn different elements. How many unique combinations can I make out of this in an n digit system when order is no importance. For example if M = {1 2} & n = 3 ...
0
votes
2answers
45 views

Two sequences $a$ and $b$ for which $\Delta a_n = \Delta b _n$

Find two different sequences $a$ and $b$ for which $\Delta a_n = \Delta b_n$ for all of $n$. This is my first time doing recurrence relations, so if anyone could provide some thorough and clear ...
0
votes
0answers
25 views

Combinatorics of relations

Let A = {1,2,3}. Find the total number of relations on A that are both symmetric and transitive. I know that there are 64 symmetric relations, but how can I find out of those how many are transitive ...
0
votes
1answer
17 views

Bound the Number of Acute-angled Triangles

I encounter the following problem with solution. But I do not quite understand the argument for 5, 10 points and eventually 100 points. Can someone elucidate the details? Problem In a plane there ...
1
vote
3answers
43 views

P white balls, Q black balls, N boxes

First of all sorry if this has been asked before, I could find "similiar" questions which seem to be harder but not quite this specific question. You are given P white balls and Q black balls, how ...
0
votes
1answer
19 views

How many functions defined on $n$ points are possible if each functional value is either $0$ or $1$?

How many functions defined on $n$ points are possible if each functional value is either $0$ or $1$? This is from the text A First Course on Probability by Sheldon Ross. The solution he ...
0
votes
0answers
20 views

Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality

The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and ...
3
votes
1answer
44 views

Ham-sandwich cut of red points and blue points in the plane.

For a finite set of points in the plane, each colored "red" or "blue", there is a line that simultaneously bisects the red points and bisects the blue points, that is, the number of red points on ...
-1
votes
0answers
16 views

Counting all possible tournament results with variable subsets removed [closed]

Given a 16 person, 4 round, single elimination tournament where the initial draw is known, what is a formula to determine the number of possible combinations if some subset(s) is removed? For example, ...
0
votes
2answers
36 views

Different values of $x$ and $y$ between $\sqrt{39}$ and $\sqrt{224}$

If $x$ and $y$ are whole numbers between $\sqrt{39}$ and $\sqrt{224}$, then how many different values can $x$ + $y$ have? OK, first I found that the set numbers are: $$7, 8 ,9 ,10 ,11 ,12, 13,14$$ ...
0
votes
1answer
36 views

Round Robin for Team Matches

My question came from the Bridge-game (Teams). This is what happens: Ideally, there are 4 pairs (A,B,C,D). We have 2 tables. In every table, there are 2 pairs. One pair is sitting in the North-South ...
1
vote
1answer
20 views

Combinatorial interpretation of identity for stirling number of second kind

I'm trying to find a combinatorial interpretation for the following identity $$S(n+1, m+1)=\sum_{k=m}^{n}\binom{n}{k}S(k,m)$$. And am having a lot of trouble thinking of one. Any pointers?
0
votes
2answers
25 views

Visualizing generalized basic principle of counting

The basic principle of counting states: Suppose that two experiments are to be performed. Then if experiment 1 can result in any one of m possible outcomes and if, for each outcome of experiment ...
0
votes
1answer
22 views

what is the number of possibilities

I have 9 variables that can vary each from 0 to 100.(natural number). And the sum of the first 3 should be between 20 and 30. And the sum of the 9 variables should be equal to 100. What is the number ...
0
votes
4answers
31 views

Finding nth term application problem

I was given this question class today and I wasn't quite sure how to solve it "There are $10$ computers all connected with a cable to each other computer" 1) How many wires are there? 2) How many ...
3
votes
2answers
102 views

Properties of a sequence of sums of binomials

I have encountered the following sequence of alternating sums of binomials and I am wondering whether there is a nicer way to write every element and/or are there some nice properties about it. So, if ...
1
vote
2answers
31 views

The binomial formula. how to show: $\Sigma_{k=0}^n k \binom{n}{k} = n2^{n-1}$ [duplicate]

Does anyone know how to show that: $\Sigma_{k=0}^n k \binom{n}{k} = n2^{n-1}$? I think we are suppose to use the binomial formula for that.. Thank you!
1
vote
2answers
65 views

Use generating functions to find the number of partitions of $n>1$ that have an odd number of even parts $k=1,…,10$

Here are some examples where we find $f(n)$ - the number of partitions that satisfy our condition: $\boldsymbol{2} = (1+1) \rightarrow \boldsymbol{f(2)=0} $ $\boldsymbol{3} = (1+1+1) = ...
2
votes
2answers
25 views

number of options to divide $n$ white balls into $r$ cells

I am trying to solve the following question: number of options to divide $n$ white balls into $r$ cells. or, more specifically: what is the number of options to divide 4 white balls into 3 cells? ...
0
votes
1answer
19 views

Sperners lemma how to mark internal vertices

Was reading sperners lemma from this http://www.math.hmc.edu/funfacts/ffiles/20001.4.shtml Couldn't understand certain things How to mark internal vertices? I could have mark some other number for ...
4
votes
1answer
55 views

How many surjective functions are there from $A=${$1,2,3,4,5$} to $B=${$1,2,3$}?

I want to find how many surjective functions there are from the set $A=${$1,2,3,4,5$} to the set $B=${$1,2,3$}? I think the best option is to count all the functions ($3^5$) and then to subtract the ...
1
vote
1answer
58 views

How many zeros does this expression end in?

How many zeroes does $$\frac{50!}{2^95^5}$$ end in?
5
votes
3answers
72 views

How many sequences of numbers $\{a_1…a_5\}$ where $a_i \in \{1…25\}$ satisfy $a_{i+1} \leq a_i + 2$

Here's how it looks: 1 1 1 1 1 1 1 1 1 2 1 1 1 1 3 1 1 1 2 1 1 1 1 2 2 1 1 1 2 3 1 1 1 2 4 1 1 1 3 1 ......... 25 25 25 25 24 25 25 25 25 25 Counting sequences ...
0
votes
2answers
35 views

Solving Problem by different Method ( non-induction)

I have this problem , which I was able to prove it by induction, but I wonder could be solve by direct method ( for example combinatorial method). I want to find number of solution for $$0 \le ...
3
votes
2answers
104 views

Counting Shaded Squares

In a $4 \times 4$ square, how many different patterns can be made by shading exactly two of the sixteen squares? Patterns that can be matched by flips and/or turns are not considered different. How ...
7
votes
2answers
33 views

The proof of $|I_X|=\frac{n!}{|\text{Aut}(X)|}$

Suppose $X$ is a graph with a set $V$ of vertices and $|V|=n$. $I_X$ is the isomorphy class of $X$ and $\text{Aut}(X)$ is the automorphism group of $X$. How can I prove the formula $$ ...
1
vote
0answers
28 views

Proof of the Catalan number formula using Dyck walks

In our notes we were given the formula $C(n)=\frac{1}{n+1}\binom{2n}{n}$ It was proved by counting the number of paths above the line y=0 from (0,0) to (2n,0) using n(1,1) up arrows and n(1,-1) down ...
1
vote
2answers
47 views

Coefficients of this generating function

For the first part of a problem, I solved the generating function to be $F(x) = \frac{x^3}{(1-x)^2}$ Now it's the easy part that has me a little confused. What would the coefficients be in this case? ...
4
votes
2answers
94 views

Green balls and Red balls, probability problem

I'm studying for my exam and I came across the following draw without replacement problem : ...